package warm100;

import java.util.HashMap;
import java.util.HashSet;

public class subarraySum_560 {

    /**
     * 子数组是数组中元素的连续非空序列
     * @return 和为 k 的子数组的个数 。
     */
    public int subarraySum(int[] nums, int k) {
        //每次迭代我们计算当前前缀和 sum，然后通过检查 sum - k (即 0 到 i 位置数字和 与 k 的 差值)
        // 是否存在于 cnt 中，如果存在说明 0-i的数组  可以截取前面的一段（0到任意位置的数字和）
        // 剩下的一段连续数组即满足和为 k 的子数组。
        // 同时更新 cnt 来记录前缀和的出现次数，供后续迭代使用。
        int sum=0,ans=0;
        HashMap<Integer,Integer> map=new HashMap<>(); //记录各种值前缀分别出现的次数
        //要预先设置一个通用前缀和0
        map.put(0,1);
        for (int i = 0; i < nums.length; i++){
            sum =sum + nums[i];
            ans+=map.getOrDefault(sum-k,0);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return ans;
    }
}
